package org.example.BinaryTree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class Fill_in_the_next_right_node_pointer_for_each_node {
    public static ArrayList<List<Node2>> arrayList = new ArrayList<>();
    public static void main(String[] args) {
        //填充每个节点的下一个右侧节点指针

        //给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
        //struct Node {
        //  int val;
        //  Node *left;
        //  Node *right;
        //  Node *next;
        //}
        //填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
        //初始状态下，所有 next 指针都被设置为 NULL。
        Node2 node1 = new Node2(1);
        Node2 node2 = new Node2(2);
        Node2 node3 = new Node2(3);
        Node2 node4 = new Node2(4);
        Node2 node5 = new Node2(5);
        Node2 root = new Node2(0);
        Node2 node6 = new Node2(6);
        Node2 node7 = new Node2(7);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node5.left = node7;
        get(root,0);
        for (List<Node2> list : arrayList) {
            Node2 node = list.get(0);
            while(node!=null){
                System.out.print(node.val+" ");
                node = node.next;
            }
            System.out.println();
        }
    }
    public static void get(Node2 root,int deep){
        if (root==null) return;
        deep++;
        if (arrayList.size()<deep){
            ArrayList<Node2> node2s = new ArrayList<>();
            arrayList.add(node2s);
            arrayList.get(deep-1).add(root);
        }else{
            int size = arrayList.get(deep - 1).size();
            arrayList.get(deep-1).get(size-1).next = root;
            arrayList.get(deep-1).add(root);
        }
        get(root.left,deep);
        get(root.right,deep);
    }

}
